本文大綱
大家好，我是半路出家、非本科系但最近開始學習程式語言當作興趣的夏。
去年此時，本著從做中學、一邊學習演算法一邊熟練Python語法的初衷，我開始每日一題Leetcode之旅，怎料越刷越覺得有趣，不知不覺半年過去後，持之以恆竟然也刷了數百題。
從一開始苦戰Medium難度，到逐漸能在Contest限時中解出一部分的Hard題，也逐漸對於「動態規劃」這個演算法中易學難精的大分類有一些心得。一直很憧憬鐵人賽的鐵人們，也從前幾屆的好文章中學到很多，剛好今年的題目有「佛心分享-刷題不只是刷題」這個主題，就決定參賽來拋磚引玉分享一下，希望能在書寫中再次梳理自己的概念，並幫助到和我一樣的初學者。
本系列文預計面向的讀者是像我一樣半路出家、沒有接觸過本科系演算法課程的初學者。如果沒有系統化的學過資料結構與演算法概念、直接上Leetcode刷題，可能Easy難度的題目能夠自力克服，但是一旦遇到暴力解無法突破、需要像是DP、DFS等等算法處理的問題時，即使有一個「能得到答案」的算法，卻未必是「時間、空間上足夠節省」的算法，就會TLE(超時)、MLE(記憶體空間不足)。
本系列文將會從動態規劃的基礎概念開始介紹，並從Easy到Hard由淺入深介紹Leetcode上各種適用動態規劃的題型，讓讀者也能掌握動態規劃的思維方式，將其舉一反三應用在題目上。
由於本文預計只會涉及動態規劃相關的概念與題型，如果和去年的我一樣完全是演算法小白，也推薦可以搭配這本帶我入門的白話演算法，內容涵蓋演算法與複雜度的基本概念，以及Binary Search、Quick Sort、DFS、BFS、Greedy...等其他刷題常見的算法。雖然這本書講的有點淺，但因為寫得很淺顯易懂，且範例都是簡單的Python語法，恰好適合新手入門。
LeetCode是目前很受歡迎的刷題練習平台，提供超過2000題不同難度的題目，涵蓋資料結構與演算法等領域。免費用戶就可以使用大多數的功能與大部分的題庫，練習題目或者參加競賽來學習或者準備面試。並且支持很多種語言，用戶可以使用自己習慣的語言來實作算法，也能參考其他人的答案。
本系列文會使用Leetcode上的題目作為範例，因此建議各位讀者註冊一個帳號，除了跟著本系列文介紹的題目練習，也可以挑戰每天的官方隨機考古題與每周末的競賽，讓學習效果更進一步！
本系列的所有文章，都會使用Python3語法作為範例，需要讀者熟悉Python的基本語法。
下文並不著重於介紹基礎語法，只會介紹幾個刷題時常用的Python語法糖與實用的函式庫。如果是完全的初學者，建議先參考網路上的常用語法教學，或者搭配Cheatsheet。
切片可以看成複製字串或者列表的一部分，但需要注意：對於嵌套列表來說，切片運算子是僅止於第一層的淺複製(Shallow Copy)
語法：直接在字串或者列表的名稱後面接中括號，規則是[開始:結束:間隔]
開始：包含。可以不寫(預設為0)
結束：不包含。可以不寫(預設為字串或者列表的長度)
間隔：可以不寫(預設為1)。如果寫2，代表每隔2個位置取一次值。如果為負值，代表反序取值。
例：
l = [0,1,2,3,4,5,6,7,8,9,10]
l[0:5:2] # [0,2,4]
l[9::-1] # [9,8,7,6,5,4,3,2,1,0]
generator(生成器)可以想像成一台機器，根據我們設定的規則來把原料「加工」成產品。
如果把產品接著放入一個list(列表)，那麼這些產品就會成為list的內容，因此又叫做list comprehension(列表生成式)。
舉例而言，如果我們需要一個0~9的平方數的列表，可以這樣寫：
lst = []
for i in range(10):
lst.append(i*i)
lst # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
而利用列表生成式，也可以這樣寫：
lst = [ i*i for i in range(10) ]
lst # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
列表生成式的寫法不僅行數較簡潔，也更容易讀出其內容。
列表生成式還能搭配判斷式使用，例如當我們要篩選一個列表中所有的偶數，可以像這樣寫：
nums = [1,2,3,4,5,6,7,8,9,10]
nums_even = [num for num in nums if num % 2 == 0]
當我們想根據簡單的規則生成列表，或者對列表內容進行簡單運算或者邏輯判斷時，列表生成式的寫法既好讀又好寫，推薦使用。
此外，生成式的寫法，不僅能用於生成list，也可以用來生成set、dict、tuple等容器資料型態，如下例：
d = {str(i)+'的平方':i*i for i in range(5)}
# {'0的平方': 0, '1的平方': 1, '2的平方': 4, '3的平方': 9, '4的平方': 16}
還可以直接作為參數，輸入「將list作為參數的函式」，例如sum、max、min、map、reduce...等，如下例：
s = sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)
# 233168 (0~999之中，被3或者5整除的整數的總和)
還可以用於建立巢狀式列表(矩陣)，如下例：
sq = [[a*b for a in range(1,10)] for b in range(1,10)]
# 九九乘法表
在後續文章的例題中，我也經常會使用這種寫法來提升程式碼的可讀性。
延伸閱讀：Medium: 生成器與迭代器
Python3的標準函式庫提供了許多實用的模組(module)，在刷題時，有些重複使用到的功能並不是演算法與資料結構的學習重點，或者不是該題主要考的觀念，重複去寫很浪費時間。此時可以適當利用這些函式庫來加快學習的腳步。
當然，第一次寫到相關概念時，還是建議自己實作看看，確保自己瞭解背後的邏輯，畢竟面試時，仍可能要求你把這部分的虛擬碼或實際的程式碼一併寫出。
如果在LeetCode上面刷題，可以不需要import，直接call函式或類别的名稱，運行時也會自動去找標準函式庫裡面同名的函式或類別。
以下先列出幾個我刷題時經常引用的模組/函式。各函式實際的使用方式，在使用到的題目的文章中會再做說明：
就是數學公式的模組，例如math.sqrt(平方根)、math.pow(N次方)、math.perm(排列數)、math.comb(組合數)、math.ceil(向上取整)...等。
像是N次方、開根號之類的，背後也有提升計算效能的演算法，如果要完整的學習演算法時，建議也花時間去了解。
比較複雜的排列組合問題，當懶得自己寫一堆for去遍歷元素排列組合的時候可以用
二元搜尋法。最常用的是bisect.bisect_left，偶爾也會用到bisect.bisect_right
因為二元搜尋法寫起來很冗，所以像Contest這種要搶時間的情境，就可以偷懶一下。
二元搜尋法本身是經常考的題目，若讀者是為了面試而刷題練習的話，一定要自己熟悉實作之後才偷懶用函式庫。
容器模組，因為基本庫只有list、dict、set、tuple，這個庫裡面實作一些比較複雜的資料結構。
和二元搜尋法一樣，資料結構本身也是常考的題目，若讀者的學習重點、考題重點是在資料結構時，務必自己實作幾次，來熟悉它們背後的概念。
若像是「動態規劃搭配OO資料結構」這種題目時，適當的引用模組，可以讓程式碼更簡潔、可讀性更好，我們練習與複習時也能比較快掌握解法中的邏輯觀念。
刷題的經驗中我常用到以下幾個類：
collections.deque 雙端佇列(Double Ended QUEue)。就是頭、尾都可以取出、放入的queue
collections.Counter 計數器。想要對list內的元素出現頻率(次數)計數時使用，並內建一些方法，例如按照出現頻率排序、取其中出現次數最高的K個元素...等等
collections.defaultdict 預設值字典。Python基本庫的dict，如果我們直接索引一個不存在的key值是會直接噴Error的。defaultdict讓我們可以設定一個預設值，當你索引時，如果有這個key，就回傳對應的value，如果沒有這個key，就將這個key的value設定成預設值。
以上都是「實作並不麻煩，但是就有點冗」的資料結構。既然都挑Python來刷題了當然要讓自己刷得爽一點對吧(誤)
實現一個heap queue(堆疊佇列)資料結構，來處理演算法中min heap或者max heap的需求。
主要用到的場合是一些Hard題，需要我們結合動態規劃與minheap來降低複雜度。
由於實作完整功能的heap真的要打很多行code，這個模組用起來就很爽。
一些裝飾器(decorator)。
裝飾器是一種高階函式/類別的語法糖，高階函式/類別可以簡單理解為：以函式作為輸入與產出的函式/類別。
在Python的語法糖中，只要在定義函式時，在def 的前一行寫@+裝飾器的名稱(裝飾子)，就可以包裝你定義的函式。
本系列文會頻繁使用@cache這個「儲存函式已計算過的答案」的功能，來提高動態規劃Top-Down策略的程式碼的可讀性。(因為每題都要寫一模一樣的東西真的很冗)
語法寫起來像是這樣
@cache # 那我幫你把算過的答案計下來，有人問我就直接幫你回答，沒人問我再問你
def lazy_func(i): # 我很懶，只想計算我還沒算過的參數
pass
在本系列前幾篇的文章中，會先手刻一次這個「儲存函式已計算過的答案」的部分，也會簡單解說@cache裝飾器的原理。
以上為Day1的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！
本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。
明天會以費波那契數列為例，介紹動態規劃的基本觀念。
iThome鐵人賽
看影片追技術